#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
using vec_int=vector<vector<int>>;
vec_int sales;
int n;
int bestcost=INT_MAX;
vector<int> bestselect;

struct Node
{
    vector<int> curpath;//当前选择的路径
    vector<bool> vis;//是否访问过
    int curcost=0;//当前花费
    int downvalue;//下界
    int curpos;//当前位置
};
struct com
{
    bool operator()(Node &x1,Node&x2)
    {
        // 最小堆
        return x1.downvalue > x2.downvalue;
    }
};
int bound(Node &x)
{
    int sum=x.curcost;
    for(int i=1;i<=n;i++)
    {
        if(!x.vis[i])
        {
            // 一个节点有n-1条出边
            int temp=INT_MAX;
            for(int j=1;j<=n;j++)
            {
                if(sales[i][j]!=-1)
                    temp=min(temp,sales[i][j]);
            }
            if(temp!=INT_MAX)sum+=temp;
        }
    }
    return sum+(sales[x.curpos][1]==-1?0:sales[x.curpos][1]);
}
// 权值：以路径花费作为权值
// 剪枝函数：如果当前的花费超过了已知的最小花费，就剪去
//    
void func(priority_queue<Node,vector<Node>,com> q)
{
    while(!q.empty())
    {
        Node now=q.top();
        q.pop();
        //剪枝
        if(now.downvalue>=bestcost)continue;

        // 判断是否为叶子结点，且可以回到原点
        if(now.curpath.size()==n&&sales[now.curpos][1]!=-1)
        {
            int totalcost=now.curcost+sales[now.curpos][1];
            if(totalcost<bestcost)
            {
                bestcost=totalcost;
                bestselect=now.curpath;
            }
        }
        // 扩展节点
        for(int i=1;i<=n;i++)
        {
            if(!now.vis[i]&&sales[now.curpos][i]!=-1)
            {
                //继承之前获得的结果
                Node next=now;
                next.curpath.push_back(i);
                next.vis[i]=true;
                next.curcost+=sales[now.curpos][i];
                next.curpos=i;
                next.downvalue=bound(next);
                // 出现可行解再加入队列中
                if(next.downvalue < bestcost)
                    q.push(next);
            }
        }
    }
}
      
int main()
{
    //首先获取有几个点，然后输入n行，每行三个数字
    // 前两个数字是两个点，最后一个点是距离，用-1代表不可达
    cout<<"请输入城市数量: ";
    cin>>n;
    sales.resize(n+1,vector<int>(n+1,-1));
    while(1)
    {
        int x,y,len;
        cin>>x>>y>>len;
        if(x==-1)break;
        sales[y][x]=sales[x][y]=len;
    }
    Node start;
    start.curpath.push_back(1);
    start.vis.resize(n+1,false);
    start.vis[1]=true;
    start.curpos=1;
    start.downvalue=bound(start);//计算下界
    priority_queue<Node,vector<Node>,com> q;

    q.push(start);
    func(q);
    if(bestcost==INT_MAX)
    {
        cout<<"没有最优解"<<endl;
    }
    else
    {
        cout<<"最优解为: "<<bestcost<<endl;
        cout<<"最优路径为: "<<endl;
        for(auto it:bestselect)
        {
            cout<<it<<" ";
        }
        cout<<1<<endl;
    }
    return 0;
}
